package leetcode_21_40;

import java.util.ArrayList;
import java.util.List;

public class combinationSum_39 {
    /**
     * 思路是递归回溯
     * 放弃
     *
     * @param candidates
     * @param target
     * @return
     */
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        function(new ArrayList<>(), candidates, 0, 0, target);
        return ans;
    }

    public static List<List<Integer>> ans = new ArrayList<>();

    public static void function(List<Integer> list, int[] nums, int i, int sum, int target) {
        if (sum == target) {
            ans.add(list);
            return;
        }
        if (sum + nums[i] < target)
            function(new ArrayList<>(), nums, i, sum, target);

    }

    /**
     * 官解
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> combine = new ArrayList<Integer>();
        dfs(candidates, target, ans, combine, 0);
        return ans;
    }

    public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
        if (idx == candidates.length) {
            return;
        }
        if (target == 0) {  //当目标值被减到0，说明为一组匹配集合
            ans.add(new ArrayList<Integer>(combine));
            return;
        }
        // 直接跳过
        dfs(candidates, target, ans, combine, idx + 1);      //因为可以重复元素，所以这里可以选择跳过当前元素，到达最后一个元素时，从后往前使用重复元素
        // 选择当前数
        if (target - candidates[idx] >= 0) { //可以继续增加元素
            combine.add(candidates[idx]);                   //直接添加元素，达到任意集合都去验证
            dfs(candidates, target - candidates[idx], ans, combine, idx);  //沿用当前元素进行判断
            combine.remove(combine.size() - 1);  //递归层层回退，顺便去除其中的元素
        }
    }

}
